package leetcode;

/**
 * 45. Jump Game II
 * 
 * @author zhujb
 *
 *         2017年9月8日
 */
public class leet045 {
	// FIXME 这个题目没看明白，先抄个别人的
	/**
	 * 
	 * @param nums
	 * @return
	 */
	public int jump(int[] nums) {

		int jumps = 0, curEnd = 0, curFarthest = 0;
		for (int i = 0; i < nums.length - 1; i++) {
			curFarthest = Math.max(curFarthest, i + nums[i]);
			if (i == curEnd) {
				jumps++;
				curEnd = curFarthest;
			}
		}
		return jumps;
	}

	public static void main(String[] args) {
		int[] nums = { 2, 3, 1, 1, 4 };

		System.out.println(new leet045().jump(nums));
	}

}
